// https://leetcode.cn/problems/target-sum/

// 题干：给你一个非负整数数组 nums 和一个整数 target 。
//       向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
//       例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
//       返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

// 示例：输入：nums = [1,1,1,1,1], target = 3
//       输出：5

// 碎语：遍历数组中的每个数字，观察到要么添加号，要么添减号
//       由此进行深搜，当i等于数组的长度的时候结束，此时如果和刚好为target，则结果加一
//       本题可以跟二叉树的所有路径作对比，可以得出对什么时候用全局变量，什么时候用局部变量有进一步的理解

#include <bits/stdc++.h>
using namespace std;

class Solution
{
    int sumWays;
    int sum;
public:
    int findTargetSumWays(vector<int>& nums, int target)
    {
        sumWays = 0, sum = 0;
        dfs(nums, 0, target);

        return sumWays;
    }

    void dfs(vector<int>& nums, int pos, int target)
    {
        if (pos == nums.size()){
            if (sum == target) sumWays++;
            return ;
        }

        // 可能是加
        sum += nums[pos];
        dfs(nums, pos + 1, target);
        sum -= nums[pos];

        // 可能是减
        sum -= nums[pos];
        dfs(nums, pos + 1, target);
        sum += nums[pos];
    }
};

int main()
{
    Solution sol;
    vector<int> nums = {1,1,1,1,1};

    cout << sol.findTargetSumWays(nums, 3) << endl;

    return 0;
}